/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class FlipStringtoMonotoneIncreasing {
	public int minFlipsMonoIncr(String S) {
		int n = S.length();
		int[][] dp = new int[n][2];

		dp[0][S.charAt(0) - '0'] = 0;
		dp[0][1 - (S.charAt(0) - '0')] = 1;
		for (int i = 1; i < n; i++) {
			if (S.charAt(i) == '0') {
				dp[i][0] = (dp[i - 1][0]);
				dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
			} else {
				dp[i][0] = dp[i - 1][0] + 1;
				dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
			}
		}
		return Math.min(dp[n - 1][0], dp[n - 1][1]);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String string = "00011000";
		System.out.println(new FlipStringtoMonotoneIncreasing().minFlipsMonoIncr(string));
	}

}
